package xyz.scootaloo.alg.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author flutterdash@qq.com
 * @since 2021/3/21 22:41
 */
public class QuickSort {

    public static int[] sort(int[] arr) {
        if (arr == null)
            throw new NullPointerException();
        if (arr.length <= 1)
            return arr;
        return sortCore(arr, 0, arr.length - 1);
    }

    private static int[] sortCore(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int pivot = arr[(left + right) / 2];
        int tmp;
        while (l < r) {
            while (arr[l] < pivot) { // 左指针向右移动，遇到大于等于中枢值为止
                l++;
            }
            while (arr[r] > pivot) { // 右指针向左移动，遇到小于等于中枢值为止
                r--;
            }
            // 左右指针已经错开，表示当前区间内[left, right]之内没有要替换的位置了
            if (l >= r)
                break;

            // swap
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            // 下面的检查是为了防止当数组内有重复的元素时，进行移动，否则会一直死循环
            if (arr[l] == pivot)
                r -= 1;
            if (arr[r] == pivot)
                l += 1;
        }

        // 左右指针碰撞，错开，否则下一轮左右区间有重复的子区间，会陷入死循环
        if (l == r) {
            l++;
            r--;
        }

        // 判断递归条件，左右区间不能重叠
        if (left < r)
            sortCore(arr, left, r);
        if (right > l)
            sortCore(arr, l, right);

        return arr;
    }

    public static void main(String[] args) {
//        int[] sample = {3, 1, 4, 2, 5, 9};
        int[] sample = {9, 9, 9, 9};
        System.out.println(Arrays.toString(sort(sample)));
    }

}
